package com.lwt.codetop.twoPointers;

import java.util.HashMap;
import java.util.Map;


// 3. 无重复字符的最长子串

/**
 * 思路：滑动窗口，使用map记录窗口内元素出现的次数，当出现重复元素时，左边要不断弹出，直到不重复
 * 时间复杂度：O(n)
 */
public class LongestSubstringWithoutRepeatingCharacters {

    public static void main(String[] args) {
        // 测试用例
        String test1 = "abcabcbb";
        String test2 = "bbbbb";
        String test3 = "pwwkew";
        System.out.println("\"abcabcbb\" 的最长无重复子串长度: " + lengthOfLongestSubstring(test1));
    }

    /**
     *  双指针维护滑动窗口，确保窗口内是补充重复的连续子串，更新答案
     *  当出现重复元素时，左边要不断弹出，直到不重复
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        int res = 0;
        int n = s.length();

        // 维护窗口的元素出现情况 cnt
        Map<Character, Integer> cnt = new HashMap<>();
        for (int i = 0, j = 0; i < n; i++) {
            char c = s.charAt(i);
            cnt.put(c, cnt.getOrDefault(c, 0) + 1); // 计数
            while (j < i && cnt.get(c) > 1) {
                char leftChar = s.charAt(j);
                cnt.put(leftChar, cnt.get(leftChar) - 1);
                j += 1;
            }
            res = Math.max(res, i - j + 1);
        }

        return res;
    }
}